package madixin.t215;

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    //快速选择
    public int findKthLargest(int[] nums, int k) {
        int l = 0;
        int r = nums.length - 1;
        k = nums.length - k;
        while (l < r) {
            int p = partition2(nums, l, r);
            if (p == k) {
                break;
            }
            if (p < k) {
                l = p + 1;
            } else {
                r = p - 1;
            }
        }
        return nums[k];
    }

    private int partition(int[] nums, int l, int r) {

        int j = l;//分界点
        //nums[l+1....j]<nums[l] ;  nums[j+1....i) > v
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] < nums[l]) {
                swap(nums, i, j + 1);
                j++;
            }
        }
        swap(nums, l, j);

        return j;
    }

    private int partition2(int[] nums, int l, int r) {
        int i = l + 1;
        int j = r;
        while (true) {
            while (i <= r && nums[i] < nums[l]) {
                i++;
            }
            while (j > l && nums[j] > nums[l]) {
                j--;
            }
            if (i > j) {
                break;
            }
            swap(nums, i, j);
            i++;
            j--;
        }
        swap(nums, l, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    //通过大顶堆实现
    public int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue(nums.length, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }

            @Override
            public boolean equals(Object obj) {
                return super.equals(obj);
            }
        });
        for (int n : nums) {
            queue.add(n);
        }

        for (int i = 0; i < k - 1; i++) {
            queue.poll();
        }
        return queue.peek();
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findKthLargest(new int[]{7, 6, 5, 4, 3, 2, 1}, 5));
        System.out.println(s.findKthLargest2(new int[]{7, 6, 5, 4, 3, 2, 1}, 5));
    }
}